//
//  main.cpp
//  heapSort
//
//  Created by Shane on 17/9/21.
//  Copyright © 2017年 Shane. All rights reserved.
//

#include <iostream>
using namespace std;


void maxHeapify(int arr[],int i,int heapsize) {      //维护堆的性质
    if (i >= heapsize -1) {
        return ;
    }
    int left = (i << 1) + 1;
    int right = left + 1;
    int largest = i;
    
    if (left < heapsize && arr[left] > arr[largest])
        largest = left;
    
    if (right < heapsize && arr[right] > arr[largest])
        largest=right;
    
    if(largest != i) {
        std::swap(arr[largest], arr[i]);
        maxHeapify(arr, largest, heapsize);
    }
}

void buildMaxHeap(int arr[], int heapsize) {          //建堆
    for(int i= heapsize/2-1; i >= 0; --i) {
        maxHeapify(arr, i, heapsize);
    }
}

void heapSort(int arr[], int len) {                   //堆排序
    buildMaxHeap(arr, len);
    for(int i = len-1; i >= 0; --i) {
        std::swap(arr[0], arr[i]);
        maxHeapify(arr, 0, --len);
    }
}


int main(int argc, const char * argv[]) {
    int a[] = {1,3,4,2,5,7,8,10,9,6};
    int count = sizeof(a)/sizeof(a[0]);
    heapSort(a, count);
    return 0;
}
